package 剑指offer;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-12-05 21:07
 * 模拟
 */
public class day25_29_31 {

    /**==============================================================================================================================================
     * 剑指 Offer 29. 顺时针打印矩阵
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
     * */
    public int[] spiralOrder(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0) return new int[0];

        int m=matrix.length,n=matrix[0].length;
        boolean[][] visited=new boolean[m][n];
        int total=m*n;
        int[] res=new int[total];
        int[][] dire=new int[][]{{0,1},{1,0},{0,-1},{-1,0}}; //右，下，左，上（顺时针）
        //标记下一个位置是哪个方向,在四个方向之间按顺序变化，当碰到边界的时候+1
        int direIndex=0;
        int row=0,col=0;
        for (int i = 0; i < total; i++) {
            res[i]=matrix[row][col];
            visited[row][col]=true;
            int nextRow=row+dire[direIndex][0],nextCol=col+dire[direIndex][1];
            if (nextRow<0||nextRow>=m||nextCol<0||nextCol>=n||visited[nextRow][nextCol]){
                //到达边界
                direIndex=(direIndex+1)%4;
            }
            row+=dire[direIndex][0];
            col+=dire[direIndex][1];
        }
        return res;
    }

    /**==============================================================================================================================================
     * 剑指 Offer 31. 栈的压入、弹出序列
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序.
     * 思路：用一个辅助栈模拟入栈出栈顺序，当入栈的时候判断当前栈顶元素是否等于出栈序列中的栈顶元素，如是则出栈，最后判断栈是否为空
     * */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int index=0;
        for (int pushnum:pushed) {
            stack.push(pushnum);
            while (!stack.isEmpty()&&stack.peek()==popped[index]){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}
